
open System.IO

let rec countAndSort(ys: int[])= 
    match ys with 
    | [| x |] -> 
        0L, [| x |]
    | ys ->  
        let leftInversions, left = countAndSort(ys.[0..(ys.Length/2 - 1)])
        let rightInversions, right = countAndSort(ys.[ys.Length/2..])
        let splitInversion = ref 0L
        let combined = ResizeArray<int>()
        let i = ref 0;
        let j = ref 0;
        while(!i < left.Length && !j < right.Length ) do
            if left.[!i] <= right.[!j]
            then 
                combined.Add(left.[!i])
                incr i
            else
                combined.Add(right.[!j])
                splitInversion := !splitInversion + int64(left.Length - !i)
                incr j

        while(!i < left.Length) do 
            combined.Add(left.[!i])
            incr i

        while(!j < right.Length) do 
            combined.Add(right.[!j])
            incr j

        let totalInversions = leftInversions + rightInversions + !splitInversion
        totalInversions, combined |> Seq.toArray

let countInversions(xs: int[]) = 
    countAndSort xs |> fst

countInversions([| 1; 3; 5; 2; 4; 6 |])
countInversions([| 1 .. 6 |])
countInversions([| 1; 3; 5; 4; 2; 6 |])

let input = File.ReadAllLines( __SOURCE_DIRECTORY__ + "\prog.assigment.input.txt") |> Array.map int
countInversions input

